【题解】 [NOI2010]超级钢琴 RMQ+优先队列 bzoj2006/洛谷P2048 | Qiuly's blog!

【题解】 [NOI2010]超级钢琴 RMQ+优先队列 bzoj2006/洛谷P2048

Posted on | Edited on | In | Comments:

这一道题显然是一道 $RMQ$ 的题目，用一个三元素组$（o，l，r）​$表示：左端点为o，右端点在l到r的区间内的最大子段，元素组用堆维护。

对于每个和弦的值，用前缀和在$O(1)$的时间复杂度求出。

$ans$累加这个三元组的贡献。由于$t$已经被选中，对于这个$o$，$t$已经不能重复选中，但最优解还可能存在于 $t$左右的两端区间中，所以提取出$(o, l, r)$之后，为了避免重复且不丧失其他较优解，我们仍然要把$(o, l, t - 1),(o, t + 1, r)$扔回堆里面去。还要避免重复或错误，即$l = t$或$r = t$的情况要进行特判。

对于$t$的位置，我们直接用ST表预处理出即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define Macth
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=500005,Log=20;
ll f[N][Log],sum[N];
template <typename Tp> inline void read(Tp &x){
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
namespace RMQ{//ST表求区间最优位置(貌似在本题中是这样)
	inline void make(int n){
	    for(register int i=1;i<=n;++i)f[i][0]=i;
        for(register int j=1;(1<<j)<=n;++j)
           for(register int i=1;i+(1<<j)-1<=n;++i){
             int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];
                f[i][j]=sum[x]>sum[y]?x:y;//取更优的位置
        }return;
    }
    inline int query(int l,int r){
	    int k=log2(r-l+1);
        int x=f[l][k],y=f[r-(1<<k)+1][k];
        return sum[x]>sum[y]?x:y;
    }
}
int n,k,L,R;
struct Queue{
	int l,r,o,t;//t就是最优的位置
	Queue(){}
	Queue(int o,int l,int r):o(o),l(l),r(r),t(RMQ::query(l,r)){}//t:取个l至r区间的最优值
	bool operator < (Queue a)const{//重载运算符
		return sum[a.t]-sum[a.o-1]<sum[t]-sum[o-1];
	}
}A;
std::priority_queue<Queue> q;
int main(){
	scanf("%d%d%d%d",&n,&k,&L,&R);
	for(register int i=1;i<=n;++i){
	    scanf("%lld",&sum[i]);sum[i]+=sum[i-1];
	}RMQ::make(n);ll ans=0;
	for(register int i=1;i<=n;++i){ 
	   if(i+L-1<=n)q.push(Queue(i,i+L-1,min(i+R-1,n)));
	}while(k--){
		A=q.top();q.pop();
		ans+=sum[A.t]-sum[A.o-1];//更新ans
		if(A.l!=A.t)q.push(Queue(A.o,A.l,A.t-1));
		if(A.r!=A.t)q.push(Queue(A.o,A.t+1,A.r));
	}printf("%lld\n",ans);
	return 0;
}

差不多就是这样了……

本文标题:【题解】 [NOI2010]超级钢琴 RMQ+优先队列 bzoj2006/洛谷P2048

文章作者:Qiuly

发布时间:2019年02月13日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP2048/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。